#include<bits/stdc++.h>
using namespace std;
const int NN=1e5+4;
vector<int>g1[NN],g2[NN];
int d[NN],gc,maxd,mind;
void dfs(int u)
{
	maxd=max(maxd,d[u]),mind=min(mind,d[u]);
	for(auto v:g1[u])
		if(d[v])
			gc=__gcd(gc,abs(d[v]-d[u]-1));
		else
		{
			d[v]=d[u]+1;
			dfs(v);
		}
	for(auto v:g2[u])
		if(d[v])
			gc=__gcd(gc,abs(d[u]-d[v]-1));
		else
		{
			d[v]=d[u]-1;
			dfs(v);
		}
}
void solve()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		g1[i].clear(),g2[i].clear(),d[i]=0;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		u++,v++;
		g1[u].push_back(v);
		g2[v].push_back(u);
	}
	gc=0;
	int res=0;
	for(int i=1;i<=n;i++)
		if(!d[i])
		{
			maxd=mind=d[i]=1e9;
			dfs(i);
			res+=maxd-mind;
		}
	if(!gc)
		gc=res;
	printf("%d\n",n-gc);
}
int main()
{
	freopen("circ.in","r",stdin);
	freopen("circ.out","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--)
		solve();
	return 0;
}
